{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Length of Subarray With Positive Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaxLen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乘积为正数的最长子数组长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>&nbsp;，请你求出乘积为正数的最长子数组的长度。</p>\n",
    "\n",
    "<p>一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。</p>\n",
    "\n",
    "<p>请你返回乘积为正数的最长子数组长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp; 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,-2,-3,4]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>数组本身乘积就是正数，值为 24 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1,-2,-3,-4]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长乘积为正数的子数组为 [1,-2,-3] ，乘积为 6 。\n",
    "注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,-2,-3,0,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10^5</code></li>\n",
    "\t<li><code>-10^9 &lt;= nums[i]&nbsp;&lt;= 10^9</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-length-of-subarray-with-positive-product](https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-length-of-subarray-with-positive-product](https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-2,-3,4]', '[0,1,-2,-3,-4]', '[-1,-2,-3,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        pre = 1\n",
    "        idx = -1\n",
    "        neg = None\n",
    "        for i, num in enumerate(nums):\n",
    "            if num > 0:\n",
    "                nums[i] = 1\n",
    "            elif num < 0:\n",
    "                nums[i] = -1\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if num < 0 and neg is None:\n",
    "                neg = i\n",
    "            if num == 0:\n",
    "                pre = 1\n",
    "                idx = i\n",
    "                neg = None\n",
    "                continue\n",
    "            else:\n",
    "                pre *= num\n",
    "                if pre > 0:\n",
    "                    ans = max(ans, i - idx)\n",
    "                else:\n",
    "                    if neg is not None:\n",
    "                        ans = max(ans, i - neg)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        def noZero(sta, end):\n",
    "            first, last = None, None\n",
    "            cnt = 0\n",
    "            for i in range(sta, end):\n",
    "                if nums[i] < 0:\n",
    "                    if first is None: first = i\n",
    "                    last = i\n",
    "                    cnt += 1\n",
    "            if cnt % 2 == 0:\n",
    "                return end-sta\n",
    "            return max(end-first-1, last-sta)\n",
    "        ans = 0\n",
    "        last = -1\n",
    "        for i, n in enumerate(nums):\n",
    "            if n == 0:\n",
    "                ans = max(ans, noZero(last+1,i))\n",
    "                last = i\n",
    "        ans = max(ans, noZero(last+1, len(nums)))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        lp, ln = 0, 0\n",
    "        mlp = 0\n",
    "        for d in nums:\n",
    "            if d > 0:\n",
    "                lp = lp + 1\n",
    "                ln = ln + 1 if ln else 0\n",
    "            elif d < 0:\n",
    "                lp, ln = ln + 1 if ln else 0, lp + 1\n",
    "            else:\n",
    "                lp, ln = 0, 0\n",
    "\n",
    "            print(d, lp, ln)\n",
    "            \n",
    "            mlp = max(lp, mlp)\n",
    "\n",
    "        return mlp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        if len(nums)==0 or (len(nums)==1 and nums[0]<=0):\n",
    "            return 0\n",
    "        if len(nums)==1 and nums[0]>0:\n",
    "            return 1\n",
    "\n",
    "        out=[0]\n",
    "       \n",
    "        len_max=1 if nums[0]>0 else 0\n",
    "\n",
    "        len_min=1 if nums[0]<0 else 0\n",
    "\n",
    "        max_len_pos=0\n",
    "\n",
    "        for ni in nums[1:]:\n",
    "            if ni>0:\n",
    "                if len_min!=0:\n",
    "                    len_min+=1\n",
    "                len_max+=1\n",
    "                \n",
    "            elif ni<0:\n",
    "                if len_min==0:\n",
    "                    len_min,len_max=len_max+1,len_min\n",
    "                else:\n",
    "                    len_min,len_max=len_max+1,len_min+1\n",
    "            else:\n",
    "                len_max,len_min=0,0\n",
    "\n",
    "            out.append(len_max)\n",
    "\n",
    "        return max(out)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp_neg =[ 0 for i in range(n+1)]\n",
    "        # dp_pos =[ 0 for i in range(n+1)]\n",
    "        dp_lneg = 0\n",
    "        dp_lpos = 0\n",
    "        dp_neg=0\n",
    "        dp_pos=0\n",
    "        re_pos = [0]\n",
    "        for i in range(n):\n",
    "            if nums[i]>0:\n",
    "                dp_pos = dp_pos+1\n",
    "                dp_neg = dp_neg+1 if dp_neg else 0\n",
    "\n",
    "            elif nums[i]<0:\n",
    "                dp_pos = dp_lneg+1 if dp_lneg else 0\n",
    "                dp_neg = dp_lpos+1 if dp_lpos else 1 \n",
    "            else:\n",
    "                dp_pos = 0\n",
    "                dp_neg = 0\n",
    "            re_pos.append(dp_pos)\n",
    "            dp_lneg = dp_neg\n",
    "            dp_lpos = dp_pos\n",
    "\n",
    "        return max(re_pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        ans,positive,negetive=0,None,None\n",
    "        for s in nums:\n",
    "            if s==0:\n",
    "                positive,negetive=None,None\n",
    "            elif s>0:\n",
    "                if positive==None:\n",
    "                    positive=1\n",
    "                else:\n",
    "                    positive+=1\n",
    "                if negetive!=None:\n",
    "                    negetive+=1\n",
    "            elif s<0:\n",
    "                if positive!=None and negetive!=None:\n",
    "                    positive,negetive=negetive+1,positive+1\n",
    "                elif positive==None:\n",
    "                    if negetive!=None:\n",
    "                        positive=negetive+1\n",
    "                    negetive=1\n",
    "                else:\n",
    "                    negetive=positive+1\n",
    "                    positive=None\n",
    "            if positive!=None:\n",
    "                ans=max(ans,positive)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dpN, dpP = 0, 0\n",
    "        if nums[0] > 0:\n",
    "            dpP = 1\n",
    "        elif nums[0] < 0:\n",
    "            dpN = 1\n",
    "        \n",
    "        ans = dpP\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                dpP = dpP + 1\n",
    "                dpN = (dpN + 1 if dpN > 0 else 0)\n",
    "            elif nums[i] < 0:\n",
    "                ndpP = (dpN + 1 if dpN > 0 else 0)\n",
    "                ndpN = dpP + 1\n",
    "                dpP, dpN = ndpP, ndpN\n",
    "            else:\n",
    "                dpP = dpN = 0\n",
    "            ans = max(ans, dpP)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        zheng, fu = 0, 0\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                zheng += 1\n",
    "            elif num < 0:\n",
    "                if fu == 0:\n",
    "                    fu, zheng = zheng+1, 0\n",
    "                else:\n",
    "                    zheng, fu = fu+zheng+1, 0\n",
    "            else:\n",
    "                zheng, fu = 0, 0\n",
    "            res = max(zheng, res)\n",
    "        \n",
    "        zheng, fu = 0, 0\n",
    "        for num in reversed(nums):\n",
    "            if num > 0:\n",
    "                zheng += 1\n",
    "            elif num < 0:\n",
    "                if fu == 0:\n",
    "                    fu, zheng = zheng+1, 0\n",
    "                else:\n",
    "                    zheng, fu = fu+zheng+1, 0\n",
    "            else:\n",
    "                zheng, fu = 0, 0\n",
    "            res = max(zheng, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        neg, pos = 0,0\n",
    "        ans = 0\n",
    "        if nums[0]<0:\n",
    "            neg = 1\n",
    "        elif nums[0]>0:\n",
    "            pos = 1\n",
    "            ans = 1\n",
    "        for num in nums[1:]:\n",
    "            if num>0:\n",
    "                neg = neg+1 if neg>0 else 0\n",
    "                pos = pos+1\n",
    "            elif num<0:\n",
    "                neg,pos = pos+1, (neg+1 if neg>0 else 0)\n",
    "            else:\n",
    "                neg = 0\n",
    "                pos = 0\n",
    "            ans = max(ans, pos)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        prod = 1\n",
    "        nums.append(0)\n",
    "        n = len(nums)\n",
    "        fp = lp = -1\n",
    "        ans = 0\n",
    "        last = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 0:\n",
    "                if prod > 0:\n",
    "                    ans = max(ans, i - last)\n",
    "                else:\n",
    "                    ans = max(ans, i - fp - 1, lp - last)\n",
    "                last = i + 1\n",
    "                fp = lp = -1\n",
    "                prod = 1\n",
    "                continue\n",
    "            if x < 0:\n",
    "                prod *= -1\n",
    "                if fp == -1:\n",
    "                    fp = i\n",
    "                lp = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        # max length of positive product, max length of negative product\n",
    "        max_pos, max_neg, res = 0, 0, 0\n",
    "        for i in nums:\n",
    "          if i == 0:\n",
    "            max_pos, max_neg = 0, 0\n",
    "          elif i > 0:\n",
    "            max_pos = max_pos + 1\n",
    "            max_neg = max_neg + 1 if max_neg > 0 else 0\n",
    "          else:\n",
    "            pre_neg = max_neg\n",
    "            max_neg = max_pos + 1\n",
    "            max_pos = pre_neg + 1 if pre_neg > 0 else 0\n",
    "          print(max_pos, max_neg)\n",
    "          res = max(res, max_pos)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums) -> int:\n",
    "        \n",
    "        # max_p 表示以前一个元素结尾的乘积为正的最长子数组长度\n",
    "        max_p = 0\n",
    "        # max_n 表示以前一个元素结尾的乘积为负的最长子数组长度\n",
    "        max_n = 0\n",
    "        ret = 0\n",
    "        \n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                max_p = 0\n",
    "                max_n = 0\n",
    "            # 如果是正数\n",
    "            elif num > 0:\n",
    "                ## p 永远加1\n",
    "                max_p = max_p + 1\n",
    "                max_n = 0 if max_n == 0 else max_n + 1\n",
    "            else:\n",
    "                ## n 永远加1\n",
    "                tmp = max_p + 1 \n",
    "                max_p = 0 if max_n == 0 else max_n + 1\n",
    "                max_n = tmp\n",
    "            \n",
    "            print(f'{num} {max_p} {max_n}')\n",
    "            ret = max(ret, max_p)\n",
    "            \n",
    "        return ret    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "\n",
    "        def zuichang(arr):#没有0的情况\n",
    "            le = len(arr)\n",
    "            z = []\n",
    "            f = []\n",
    "            for i in range(le):\n",
    "                if arr[i] < 0:\n",
    "                    f.append(i)\n",
    "                else:\n",
    "                    z.append(i)\n",
    "\n",
    "            if len(f)%2 == 0:\n",
    "                o = le\n",
    "            else:\n",
    "                o = max(f[0],le-f[0]-1,le-f[-1]-1,f[-1])\n",
    "            return o\n",
    "        if 0 not in nums:#没0的情况\n",
    "            o = zuichang(nums)\n",
    "            return o\n",
    "        else:#有0的情况\n",
    "            l =[]\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 0:\n",
    "                    l.append(i)\n",
    "\n",
    "            if len(l) == 1:#有1个0存在的情况\n",
    "                a = nums[:l[0]]\n",
    "                b = nums[l[0]+1:]\n",
    "                o1 = zuichang(a)\n",
    "                o2 = zuichang(b)\n",
    "                o = max(o1,o2)\n",
    "                return o\n",
    "            else:#有2个以上0\n",
    "                o = 0\n",
    "                for i in range(len(l)):\n",
    "                    if i == 0:\n",
    "                        nums0 = nums[:l[i]]\n",
    "                        o = max(o,zuichang(nums0))\n",
    "                    elif i == len(l)-1:\n",
    "                        numsr = nums[l[i]+1:]\n",
    "                        numsl = nums[l[i-1]+1:l[i]]\n",
    "                        o = max(o,zuichang(numsl),zuichang(numsr))\n",
    "                    else:\n",
    "                        numsz =  nums[l[i-1]+1:l[i]]\n",
    "                        o = max(o,zuichang(numsz))\n",
    "                return o\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        cnt = [0]*2\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] > 0:\n",
    "                cnt[1] += 1\n",
    "                cnt[0] += 1 if cnt[0] else 0\n",
    "            elif nums[i] < 0:\n",
    "                cnt[1], cnt[0] = cnt[0]+1 if cnt[0] else 0, cnt[1]+1\n",
    "            else:\n",
    "                cnt = [0]*2\n",
    "            print(cnt)\n",
    "            ret = max(ret, cnt[1])\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        pos = [0]*n\r\n",
    "        neg = [0]*n\r\n",
    "        if nums[0] > 0:\r\n",
    "            pos[0] = 1\r\n",
    "        if nums[0] < 0:\r\n",
    "            neg[0] = 1\r\n",
    "        ans = pos[0]\r\n",
    "        for i in range(1,n):\r\n",
    "            if nums[i] > 0:\r\n",
    "                pos[i] = pos[i-1] + 1\r\n",
    "                neg[i] = neg[i-1] + 1 if neg[i-1] > 0 else 0\r\n",
    "            elif nums[i] < 0:\r\n",
    "                pos[i] = neg[i - 1] + 1 if neg[i-1] > 0 else 0\r\n",
    "                neg[i] = pos[i-1] + 1\r\n",
    "            else:\r\n",
    "                pos[i] = neg[i] = 0\r\n",
    "            ans = max(ans, pos[i])\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        def longest(n_l:list):\n",
    "            if n_l.count( -1 ) % 2 == 0:return len(n_l)\n",
    "            else:\n",
    "                i = n_l.index(-1)\n",
    "                j = n_l[::-1].index((-1))\n",
    "                return max(len(n_l)-i-1, len(n_l)-j-1)\n",
    "        new_nums = list(map(lambda x: 1 if x > 0 else -1 if x < 0 else 0, nums))\n",
    "        ans = 0\n",
    "        if new_nums.count(0) == 0:\n",
    "            return longest(new_nums)\n",
    "        zero_nums = [i for i in range(len(new_nums)) if new_nums[i] == 0]\n",
    "        zero_nums = [-1] + zero_nums + [len(new_nums)]\n",
    "        for i in range(len(zero_nums) -1):\n",
    "            ans = max(ans, longest(new_nums[zero_nums[i]+1:zero_nums[i+1]]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        def longest(n_l:list):\n",
    "            if n_l.count( -1 ) % 2 == 0:return len(n_l)\n",
    "            else:\n",
    "                i = n_l.index(-1)\n",
    "                j = n_l[::-1].index((-1))\n",
    "                return max(len(n_l)-i-1, len(n_l)-j-1)\n",
    "        def check(x:int):\n",
    "            if x > 0:return 1\n",
    "            elif x == 0:return 0\n",
    "            else:return -1\n",
    "        new_nums = list(map(check, nums))\n",
    "        ans = 0\n",
    "        # if new_nums.count(0) == 0:\n",
    "        #     return longest(new_nums)\n",
    "        left = -1\n",
    "        new_nums.append(0)\n",
    "        for i in range(len(new_nums)):\n",
    "            if new_nums[i] == 0:\n",
    "                if i - left > ans:\n",
    "                    ans = max(ans, longest(new_nums[left + 1:i]))\n",
    "                left = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        def longest(n_l:list):\n",
    "            if n_l.count( -1 ) % 2 == 0:return len(n_l)\n",
    "            else:\n",
    "                i = j = 0\n",
    "                for i in range(len(n_l)):\n",
    "                    if n_l[i] == -1:break\n",
    "                for j in range(len(n_l) -1, -1, -1):\n",
    "                    if n_l[j] == -1:break\n",
    "                return max(len(n_l)-i-1, j)\n",
    "        new_nums = list(map(lambda x: 1 if x > 0 else -1 if x < 0 else 0, nums))\n",
    "        ans = 0\n",
    "        if new_nums.count(0) == 0:\n",
    "            return longest(new_nums)\n",
    "        zero_nums = [i for i in range(len(new_nums)) if new_nums[i] == 0]\n",
    "        zero_nums = [-1] + zero_nums + [len(new_nums)]\n",
    "        for i in range(len(zero_nums) -1):\n",
    "            ans = max(ans, longest(new_nums[zero_nums[i]+1:zero_nums[i+1]]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        zero_nums = [-1]\n",
    "        self.k = -1\n",
    "        def longest(n_l:list):\n",
    "            if n_l.count( -1 ) % 2 == 0:return len(n_l)\n",
    "            else:\n",
    "                i = n_l.index(-1)\n",
    "                j = n_l[::-1].index((-1))\n",
    "                return max(len(n_l)-i-1, len(n_l)-j-1)\n",
    "        def check(x:int):\n",
    "            self.k += 1\n",
    "            if x > 0:return 1\n",
    "            elif x == 0:zero_nums.append(self.k);return 0\n",
    "            else:return -1\n",
    "        new_nums = list(map(check, nums))\n",
    "        ans = 0\n",
    "        zero_nums.append(len(new_nums))\n",
    "        if len(zero_nums) == 2:return longest(new_nums)\n",
    "        # if new_nums.count(0) == 0:\n",
    "        #     return longest(new_nums)\n",
    "        # zero_nums = [i for i in range(len(new_nums)) if new_nums[i] == 0]\n",
    "        # zero_nums = [-1] + zero_nums + [len(new_nums)]\n",
    "        for i in range(len(zero_nums) -1):\n",
    "            ans = max(ans, longest(new_nums[zero_nums[i]+1:zero_nums[i+1]]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        \n",
    "        def getSymbols(nums):\n",
    "            res = 1\n",
    "            for x in nums:\n",
    "                if res*x>0:\n",
    "                    res = 1\n",
    "                else:\n",
    "                    res = -1\n",
    "            return res\n",
    "        \n",
    "        def getMaxLen(nums):\n",
    "            index_t = []\n",
    "            l = len(nums)\n",
    "            for i in range(l):\n",
    "                if nums[i] < 0:\n",
    "                    index_t.append(i)\n",
    "                    break\n",
    "            for j in range(l)[::-1]:\n",
    "                if nums[j] < 0:\n",
    "                    index_t.append(j)\n",
    "                    break\n",
    "            return max(l-index_t[0]-1, index_t[1])\n",
    "\n",
    "        result = []\n",
    "        tmp = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != 0:\n",
    "                tmp.append(nums[i])\n",
    "            else:\n",
    "                if len(tmp) > 0:\n",
    "                    result.append(tmp)\n",
    "                tmp = []\n",
    "        if len(tmp) > 0:\n",
    "            result.append(tmp)\n",
    "        result.sort(key = lambda x:len(x), reverse = True)\n",
    "        curr_max = -1\n",
    "        for i in range(len(result)):\n",
    "            if curr_max >= len(result[i]):\n",
    "                return curr_max\n",
    "            elif getSymbols(result[i]) == 1:\n",
    "                return len(result[i])\n",
    "            else:\n",
    "                g = getMaxLen(result[i])\n",
    "                if g > curr_max:\n",
    "                    curr_max = g\n",
    "        if curr_max == -1:\n",
    "            return 0\n",
    "        return(curr_max)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        nums.append(0)\n",
    "        tmp = nums[:]\n",
    "        tmp.reverse()\n",
    "        nums.extend(tmp)\n",
    "        max_length = 0\n",
    "        Sum = 1\n",
    "        length = 0\n",
    "        for num in nums:\n",
    "            Sum *= num\n",
    "            length += 1\n",
    "            if Sum > 0:\n",
    "                max_length = max(max_length,length)\n",
    "                Sum = 1\n",
    "            elif Sum ==0:\n",
    "                Sum = 1\n",
    "                length = 0\n",
    "            else:\n",
    "                Sum = -1\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        positive, negative = [0] * length, [0] * length\n",
    "        if nums[0] > 0:\n",
    "            positive[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            negative[0] = 1\n",
    "        \n",
    "        maxLength = positive[0]\n",
    "        for i in range(1, length):\n",
    "            if nums[i] > 0:\n",
    "                positive[i] = positive[i - 1] + 1\n",
    "                negative[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)\n",
    "            elif nums[i] < 0:\n",
    "                positive[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)\n",
    "                negative[i] = positive[i - 1] + 1\n",
    "            else:\n",
    "                positive[i] = negative[i] = 0\n",
    "            maxLength = max(maxLength, positive[i])\n",
    "\n",
    "        return maxLength\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "         # nums插入0，在nums后加入翻转nums的值，以免出现负数在前的情况\n",
    "        nums.append(0)\n",
    "        tep = nums[:]\n",
    "        tep.reverse()\n",
    "        nums.extend(tep)\n",
    "\n",
    "        # sum 有0 1 -1 三种情况\n",
    "        Sum = 1\n",
    "        length = 0\n",
    "        MaxLong = 0\n",
    "        for item in nums:\n",
    "            Sum *= item\n",
    "            length += 1\n",
    "            if Sum > 0:\n",
    "                MaxLong = max(MaxLong, length)\n",
    "                Sum = 1\n",
    "            elif Sum == 0:\n",
    "                length = 0\n",
    "                Sum = 1\n",
    "            else:\n",
    "                Sum = -1\n",
    "        return MaxLong"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        pos = [1 if nums[0]>0 else 0]\n",
    "        neg = [1 if nums[0]<0 else 0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i]==0:\n",
    "                pos.append(0)\n",
    "                neg.append(0)\n",
    "            elif nums[i]>0:\n",
    "                pos.append(pos[-1]+1)\n",
    "                if neg[-1]==0:\n",
    "                    neg.append(0)\n",
    "                else:\n",
    "                    neg.append(neg[-1]+1)\n",
    "            else:\n",
    "                if neg[-1]==0:\n",
    "                    pos.append(0)\n",
    "                else:\n",
    "                    pos.append(neg[-1]+1)\n",
    "                neg.append(pos[i-1]+1)\n",
    "\n",
    "        print(pos) \n",
    "        print(neg)           \n",
    "        return max(pos)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        positive, negative = [0] * length, [0] * length\n",
    "        if nums[0] > 0:\n",
    "            positive[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            negative[0] = 1\n",
    "        \n",
    "        maxLength = positive[0]\n",
    "        for i in range(1, length):\n",
    "            if nums[i] > 0:\n",
    "                positive[i] = positive[i - 1] + 1\n",
    "                negative[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)\n",
    "            elif nums[i] < 0:\n",
    "                positive[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)\n",
    "                negative[i] = positive[i - 1] + 1\n",
    "            else:\n",
    "                positive[i] = negative[i] = 0\n",
    "            maxLength = max(maxLength, positive[i])\n",
    "\n",
    "        return maxLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        positive = [0] * n\n",
    "        negative = [0] * n \n",
    "        if nums[0] > 0:\n",
    "            positive[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            negative[0] = 1\n",
    "        maxLength = positive[0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > 0:\n",
    "                positive[i] = positive[i-1] + 1\n",
    "                negative[i] = (negative[i-1] + 1 if negative[i-1] > 0 else 0)\n",
    "\n",
    "            elif nums[i] < 0:\n",
    "                positive[i] = (negative[i-1] + 1 if negative[i-1] > 0 else 0)\n",
    "                negative[i] = positive[i-1] + 1 \n",
    "            else:\n",
    "                positive[i] = negative[i] = 0\n",
    "            maxLength = max(maxLength, positive[i])\n",
    "        return maxLength"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp_pos = [0] * len(nums)\n",
    "        dp_neg = [0] * len(nums)\n",
    "        if nums[0] > 0:\n",
    "            dp_pos[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            dp_neg[0] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                dp_pos[i] = dp_pos[i-1] + 1\n",
    "                dp_neg[i] = dp_neg[i-1] + 1 if dp_neg[i-1] > 0 else 0\n",
    "            elif nums[i] < 0:\n",
    "                dp_pos[i] = dp_neg[i-1] + 1 if dp_neg[i-1] > 0 else 0\n",
    "                dp_neg[i] = dp_pos[i-1] + 1\n",
    "            else:\n",
    "                dp_pos[i] = 0\n",
    "                dp_neg[i] = 0\n",
    "        # print(dp_pos)\n",
    "        # print(dp_neg)\n",
    "        return max(dp_pos)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # plus[i]: length of longest positive subarray ends with nums[i]\n",
    "        # minus[i]: length of longest negative subarray ends with nums[i]\n",
    "        plus, minus = [0]*(n+1), [0]*(n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            if nums[i] > 0:\n",
    "                plus[i+1] = plus[i]+1\n",
    "                minus[i+1] = 0 if minus[i] == 0 else minus[i]+1\n",
    "            elif nums[i] < 0:\n",
    "                plus[i+1] = minus[i]+1 if minus[i] != 0 else 0\n",
    "                minus[i+1] = plus[i]+1\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "\n",
    "        return max(plus)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int: \n",
    "        n = len(nums)\n",
    "        pos = [1] * n\n",
    "        neg = [1] * n\n",
    "        if nums[0] > 0:\n",
    "            pos[0] = 1\n",
    "            neg[0] = 0\n",
    "        elif nums[0] < 0:\n",
    "            pos[0] = 0\n",
    "            neg[0] = 1\n",
    "        else:\n",
    "            pos[0] = 0\n",
    "            neg[0] = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > 0:\n",
    "                pos[i] = pos[i-1]+1\n",
    "                neg[i] = neg[i-1] > 0 and neg[i-1]+1 or 0\n",
    "            elif nums[i] < 0:\n",
    "                pos[i] = neg[i-1] > 0 and neg[i-1]+1 or 0\n",
    "                neg[i] = pos[i-1]+1    \n",
    "            else:\n",
    "                pos[i] = 0\n",
    "                neg[i] = 0\n",
    "        return max(pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos = [0] * n\n",
    "        neg = [0] * n\n",
    "        if nums[0] > 0:\n",
    "            pos[0] = 1\n",
    "        if nums[0] < 0:\n",
    "            neg[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 0:\n",
    "                continue\n",
    "            elif nums[i] > 0:\n",
    "                pos[i] = pos[i - 1] + 1\n",
    "                if neg[i - 1] > 0:\n",
    "                    neg[i] = neg[i - 1] + 1\n",
    "            elif nums[i] < 0:\n",
    "                if neg[i - 1] > 0:\n",
    "                    pos[i] = neg[i - 1] + 1\n",
    "                neg[i] = pos[i - 1] + 1\n",
    "        print(nums)\n",
    "        print(pos)\n",
    "        print(neg)\n",
    "        return max(pos) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "\n",
    "        n = len(nums)\n",
    "        dp_pos = [0] * (n + 1)\n",
    "        dp_neg = [0] * (n + 1)\n",
    "\n",
    "        for i, num in enumerate(nums):            \n",
    "            if num > 0:\n",
    "                dp_pos[i+1] = dp_pos[i] + 1\n",
    "                dp_neg[i+1] = dp_neg[i] + 1 if dp_neg[i] != 0 else 0\n",
    "            elif num < 0:\n",
    "                dp_neg[i+1] = dp_pos[i] + 1\n",
    "                dp_pos[i+1] = dp_neg[i] + 1 if dp_neg[i] != 0 else 0\n",
    "            else:\n",
    "                dp_neg[i+1] = 0\n",
    "                dp_pos[i+1] = 0\n",
    "            \n",
    "            ret = max(ret, dp_pos[i+1])\n",
    "        print(dp_pos)\n",
    "        print(dp_neg)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos, mis = [_ for _ in range(n)], [_ for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                pos[i] = 0\n",
    "                mis[i] = 0\n",
    "            elif num > 0:\n",
    "                pos[i] = pos[i - 1] + 1 if i > 0 and pos[i - 1] != 0 else 1\n",
    "                mis[i] = mis[i - 1] + 1 if i > 0 and mis[i - 1] != 0 else 0\n",
    "            elif num < 0:\n",
    "                pos[i] = mis[i - 1] + 1 if i > 0 and mis[i - 1] != 0 else 0\n",
    "                mis[i] = pos[i - 1] + 1 if i > 0 and pos[i - 1] != 0 else 1\n",
    "        print(pos)\n",
    "        print(mis)\n",
    "        return max(pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, a: List[int]) -> int:\n",
    "        pos = [0] * 100005 # 以a[i]为结尾的乘积为正数的最长子数组长度\n",
    "        neg = [0] * 100005 # 以a[i]为结尾的乘积为负数的最长子数组长度\n",
    "        pos[0] += int(a[0]>0)\n",
    "        neg[0] += int(a[0]<0)\n",
    "        n = len(a)\n",
    "        for i in range(1, n):\n",
    "            if a[i] == 0:\n",
    "                pos[i] = neg[i] = 0\n",
    "            if a[i] > 0:\n",
    "                if pos[i-1] > 0:\n",
    "                    pos[i] = pos[i-1] + 1\n",
    "                else:\n",
    "                    pos[i] = 1\n",
    "                \n",
    "                if neg[i-1] > 0:\n",
    "                    neg[i] = neg[i-1]+1\n",
    "                else:\n",
    "                    neg[i] = 0\n",
    "            if a[i] < 0:\n",
    "                if neg[i-1] > 0:\n",
    "                    pos[i] = neg[i-1] + 1\n",
    "                else:\n",
    "                    pos[i] = 0\n",
    "                \n",
    "                if pos[i-1] > 0:\n",
    "                    neg[i] = pos[i-1] + 1\n",
    "                else:\n",
    "                    neg[i] = 1\n",
    "\n",
    "        return max(pos[:n])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        pos = [0]\n",
    "        neg = [0]\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                pos.append(pos[-1] + 1)\n",
    "                neg.append(neg[-1] + 1 if neg[-1] != 0 else 0)\n",
    "            elif num < 0:\n",
    "                pos.append(neg[-1] + 1 if neg[-1] != 0 else 0)\n",
    "                neg.append(pos[-2] + 1)\n",
    "            else:\n",
    "                pos.append(0)\n",
    "                neg.append(0)\n",
    "\n",
    "        print(pos)\n",
    "        print(neg)\n",
    "        return max(pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        def solve(nums):\n",
    "            if not nums:\n",
    "                return 0\n",
    "            dp = [[0 for i in range(len(nums))] for j in range(2)]\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i]>0:\n",
    "                    dp[0][i] = 1\n",
    "                else:\n",
    "                    dp[1][i] = 1\n",
    "            max_length = dp[0][0]\n",
    "            for i in range(1,len(nums)):\n",
    "                if nums[i] >0:\n",
    "                    if dp[0][i-1]>0:\n",
    "                        dp[0][i] = max(dp[0][i],dp[0][i-1]+1)\n",
    "                    if dp[1][i-1] > 0 :\n",
    "                        dp[1][i] = max(dp[1][i],dp[1][i-1]+1)\n",
    "\n",
    "                elif nums[i] <0:\n",
    "                    if dp[1][i-1] > 0 :\n",
    "                        dp[0][i] = max(dp[0][i],dp[1][i-1]+1)\n",
    "                    if dp[0][i-1] > 0 :\n",
    "                        dp[1][i] = max(dp[1][i],dp[0][i-1]+1)\n",
    "\n",
    "                max_length = max(max_length,dp[0][i])\n",
    "            print(dp)\n",
    "            return max_length\n",
    "        \n",
    "        \n",
    "        nums = [0] + nums + [0]\n",
    "        start = 0\n",
    "        ans = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            elif nums[i] == 0:\n",
    "                ans = max(ans,solve(nums[start+1:i]))\n",
    "                start = i\n",
    "                \n",
    "        return ans\n",
    "                \n",
    "        \n",
    "        \n",
    "                    \n",
    "                \n",
    "                \n",
    "            \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        length, maxlen, index = len(nums), 0, None\n",
    "        if length == 1:\n",
    "            return 1 if nums[0] > 0 else 0\n",
    "        if nums[0] > 0:\n",
    "            res = [[1, 0]]\n",
    "        elif nums[0] < 0:\n",
    "            res = [[0, 1]]\n",
    "        else:\n",
    "            res = [[0, 0]]\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            if nums[i] > 0:\n",
    "                res.append([res[i-1][0] + 1, res[i-1][1]])\n",
    "            elif nums[i] < 0:\n",
    "                res.append([res[i-1][0], res[i-1][1] + 1])  \n",
    "            else:\n",
    "                res.append([0, 0])\n",
    "                \n",
    "        \n",
    "        for i in range(length):\n",
    "            if res[i] == [0, 0]:\n",
    "                index = None\n",
    "            if res[i][1] % 2 == 0:\n",
    "                maxlen = max(maxlen, sum(res[i]))\n",
    "            else:\n",
    "                if index is None:\n",
    "                    index = i\n",
    "                else:\n",
    "                    maxlen = max(maxlen, sum(res[i]) - sum(res[index]))\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp1 = [0] * n\n",
    "        dp2 = [0] * n\n",
    "        if nums[0] > 0:\n",
    "            dp1[0] = 1\n",
    "        if nums[0] < 0:\n",
    "            dp2[0] = 1 \n",
    "        maxLength = dp1[0]\n",
    "        for i in range(1,n):\n",
    "            if nums[i] == 0:\n",
    "                dp1[i] = 0\n",
    "                dp2[i] = 0\n",
    "            elif nums[i] > 0:\n",
    "                dp1[i] = dp1[i-1] + 1\n",
    "                if dp2[i-1] > 0:\n",
    "                    dp2[i] = dp2[i-1] + 1\n",
    "            else:\n",
    "                dp2[i] = dp1[i-1] + 1\n",
    "                if dp2[i-1] > 0:\n",
    "                    dp1[i] = dp2[i-1] + 1\n",
    "            maxLength = max(dp1[i],maxLength)\n",
    "        print(nums)\n",
    "        print(dp1)\n",
    "        print(dp2)\n",
    "        return maxLength\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        prefix, m, n, q, res = [0] * len(nums), 0, 0, -1, 0\n",
    "        for i, e in enumerate(nums):\n",
    "            if not e:\n",
    "                m=n=0\n",
    "                q = -1\n",
    "            elif e > 0:\n",
    "                m += 1\n",
    "            else:\n",
    "                if q == -1:\n",
    "                    q = i\n",
    "                n += 1\n",
    "            prefix[i] = [m,n]\n",
    "            if (n & 1):\n",
    "                pm, pn = prefix[q]\n",
    "                res = max(res,m-pm+n-pn)\n",
    "            else:\n",
    "                res = max(res, m + n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n  # 记录最大长度\n",
    "        m = [0] * n  # 记录负数的个数\n",
    "        p = 0\n",
    "        if nums[0] > 0:\n",
    "            dp[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            m[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 0:\n",
    "                dp[i] = 0\n",
    "                m[i] = 0\n",
    "                continue\n",
    "            if nums[i] < 0:\n",
    "                m[i] += m[i - 1] + 1\n",
    "                if m[i] % 2 == 0:\n",
    "                    dp[i] += dp[p] + i - p + 1\n",
    "                else:\n",
    "                    p = i\n",
    "                    dp[i] += dp[i - 1]\n",
    "            elif nums[i] > 0:\n",
    "                m[i] = m[i - 1]\n",
    "                if m[i] % 2 == 0:\n",
    "                    dp[i] += dp[i - 1] + 1\n",
    "                else:\n",
    "                    dp[i] = max(dp[i - 1],i-p)\n",
    "        a=max(dp)\n",
    "        nums = nums[::-1]\n",
    "        n = len(nums)\n",
    "        dp1 = [0] * n  # 记录最大长度\n",
    "        m1 = [0] * n  # 记录负数的个数\n",
    "        p = 0\n",
    "        if nums[0] > 0:\n",
    "            dp1[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            m1[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 0:\n",
    "                dp1[i] = 0\n",
    "                m1[i] = 0\n",
    "                continue\n",
    "            if nums[i] < 0:\n",
    "                m1[i] += m1[i - 1] + 1\n",
    "                if m1[i] % 2 == 0:\n",
    "                    dp1[i] += dp1[p] + i - p + 1\n",
    "                else:\n",
    "                    p = i\n",
    "                    dp1[i] += dp1[i - 1]\n",
    "            elif nums[i] > 0:\n",
    "                m1[i] = m1[i - 1]\n",
    "                if m1[i] % 2 == 0:\n",
    "                    dp1[i] += dp1[i - 1] + 1\n",
    "                else:\n",
    "                    dp1[i] = max(dp1[i - 1], i - p)\n",
    "        b = max(dp1)\n",
    "        return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n  # 记录最大长度\n",
    "        m = [0] * n  # 记录负数的个数\n",
    "        p = 0\n",
    "        if nums[0] > 0:\n",
    "            dp[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            m[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 0:\n",
    "                dp[i] = 0\n",
    "                m[i] = 0\n",
    "                continue\n",
    "            if nums[i] < 0:\n",
    "                m[i] += m[i - 1] + 1\n",
    "                if m[i] % 2 == 0:\n",
    "                    dp[i] += dp[p] + i - p + 1\n",
    "                else:\n",
    "                    p = i\n",
    "                    dp[i] += dp[i - 1]\n",
    "            elif nums[i] > 0:\n",
    "                m[i] = m[i - 1]\n",
    "                if m[i] % 2 == 0:\n",
    "                    dp[i] += dp[i - 1] + 1\n",
    "                else:\n",
    "                    dp[i] = max(dp[i - 1],i-p)\n",
    "        a=max(dp)\n",
    "        nums = nums[::-1]\n",
    "        n = len(nums)\n",
    "        dp1 = [0] * n  # 记录最大长度\n",
    "        m1 = [0] * n  # 记录负数的个数\n",
    "        p = 0\n",
    "        if nums[0] > 0:\n",
    "            dp1[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            m1[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 0:\n",
    "                dp1[i] = 0\n",
    "                m1[i] = 0\n",
    "                continue\n",
    "            if nums[i] < 0:\n",
    "                m1[i] += m1[i - 1] + 1\n",
    "                if m1[i] % 2 == 0:\n",
    "                    dp1[i] += dp1[p] + i - p + 1\n",
    "                else:\n",
    "                    p = i\n",
    "                    dp1[i] += dp1[i - 1]\n",
    "            elif nums[i] > 0:\n",
    "                m1[i] = m1[i - 1]\n",
    "                if m1[i] % 2 == 0:\n",
    "                    dp1[i] += dp1[i - 1] + 1\n",
    "                else:\n",
    "                    dp1[i] = max(dp1[i - 1], i - p)\n",
    "        b = max(dp1)\n",
    "        return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1: return 1 if nums[0] > 0 else 0\n",
    "        if nums[0] > 0:\n",
    "            res = [[1, 0]] + [[0, 0]] * (length - 1)\n",
    "        elif nums[0] < 0:\n",
    "            res = [[0, 1]] + [[0, 0]] * (length - 1)\n",
    "        else:\n",
    "            res = [[0, 0]] * length\n",
    "        \n",
    "        for i in range(1, length):\n",
    "            if nums[i] > 0:\n",
    "                res[i] = [res[i-1][0] + 1, res[i-1][1]]\n",
    "            elif nums[i] < 0:\n",
    "                res[i] = [res[i-1][0], res[i-1][1] + 1]\n",
    "        \n",
    "        print(res)\n",
    "        maxlen = 0\n",
    "        index = None\n",
    "        for i in range(length):\n",
    "            if res[i] == [0, 0]:\n",
    "                index = None\n",
    "            if res[i][1] % 2 == 0:\n",
    "                maxlen = max(maxlen, sum(res[i]))\n",
    "            else:\n",
    "                if index is None:\n",
    "                    index = i\n",
    "                else:\n",
    "                    maxlen = max(maxlen, sum(res[i]) - sum(res[index]))\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        def dp(l,r):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            elif 0 in nums[l:r]:\n",
    "                return max(dp(l,l+nums[l:r].index(0)),dp(l+nums[l:r].index(0)+1,r))\n",
    "            else:\n",
    "                if len([n for n in nums[l:r] if n<0])%2==0:\n",
    "                    return r-l\n",
    "                else:\n",
    "                    for i in range(r-l):\n",
    "                        if nums[l+i]<0 or nums[r-i-1]<0:\n",
    "                            return r-l-i-1\n",
    "        return dp(0,len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp[i][0]表示以nums[i-1]结尾的，最长乘积为正数的子数组长度\n",
    "        # dp[i][1]表示以nums[i-1]结尾的，最长乘积为负数的子数组长度\n",
    "        # 这里以nums[i-1]结尾，是为了不需要考虑边界条件\n",
    "        # 最后的结果应该是dp[:][0]中的最大值\n",
    "        dp = [[0,0] for _ in range(n+1)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            # 对于每个数nums[i]，对应的为dp[i+1]。\n",
    "            # 如果大于0，那么dp[i][0]直接加1，如果dp[i][1]存在，则负*正为负，dp[i][1]+1\n",
    "            if nums[i] > 0:\n",
    "                dp[i+1][0] = dp[i][0] + 1              \n",
    "                dp[i+1][1] = dp[i][1] + 1 if dp[i][1] else 0\n",
    "            # 如果小于0，与上面同理\n",
    "            elif nums[i] < 0:\n",
    "                dp[i+1][0] = dp[i][1] + 1  if dp[i][1] else 0\n",
    "                dp[i+1][1] = dp[i][0] + 1\n",
    "            # 如果为0，则重置为[0,0]\n",
    "            else:\n",
    "                dp[i+1] = [0,0]   \n",
    "            # 使用res来保存最大的长度       \n",
    "            res = max(res,dp[i+1][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        data = [() for x in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            n = nums[i]\n",
    "            if n == 0:\n",
    "                data[i] = (0, 0, 0)\n",
    "                continue\n",
    "            if i == 0 or data[i-1][0] == 0:\n",
    "                if n > 0:\n",
    "                    _tp = (1, 1, 0)\n",
    "                else:\n",
    "                    _tp = (-1, 0, 1)\n",
    "                data[i] = _tp\n",
    "                continue\n",
    "            t0, t1, t2 = data[i - 1]\n",
    "            _t = t2 + 1 if t2 > 0 else t2\n",
    "            if n > 0:\n",
    "                _tp = (t0, t1 + 1, _t)\n",
    "            else:\n",
    "                _tp = (t0*(-1), _t, t1 + 1)\n",
    "            data[i] = _tp\n",
    "        return max([x[1] for x in data])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        total = len(nums)\n",
    "        if total == 1:\n",
    "            return 1 if nums[0] > 0 else 0\n",
    "        if nums[0] > 0:\n",
    "            dp = [(1, 0)]\n",
    "        elif nums[0] < 0:\n",
    "            dp = [(0, 1)]\n",
    "        else:\n",
    "            dp = [(0, 0)]\n",
    "        for i in range(1, total):\n",
    "            if nums[i] > 0:\n",
    "                dp.append((dp[-1][0] + 1, 0 if dp[-1][1] == 0 else (dp[-1][1] + 1)))\n",
    "            elif nums[i] < 0:\n",
    "                dp.append((0 if dp[-1][1] == 0 else (dp[-1][1] + 1), dp[-1][0] + 1))\n",
    "            else:\n",
    "                dp.append((0, 0))\n",
    "        return max(dp, key=lambda x: x[0])[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [(0, 0) for _ in range(n+1)]\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            posi, nega = dp[i-1]\n",
    "            if nums[i-1] == 0:\n",
    "                dp[i] = (0, 0)\n",
    "            elif nums[i-1] > 0:\n",
    "                dp[i] = (posi+1, 0 if nega == 0 else nega+1)\n",
    "            else:\n",
    "                dp[i] = (0 if nega == 0 else nega+1, posi+1)\n",
    "            res = max(res, dp[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp = [[0, 0] for _ in range(len(nums) + 1)]\n",
    "        max_len = 0\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            pos, neg = dp[i - 1]\n",
    "            if nums[i - 1] == 0:\n",
    "                dp[i] = [0, 0]\n",
    "            elif nums[i - 1] > 0:\n",
    "                dp[i][0] = pos + 1\n",
    "                dp[i][1] = neg + 1 if neg else 0\n",
    "            else:\n",
    "                dp[i][0] = neg + 1 if neg else 0\n",
    "                dp[i][1] = pos + 1\n",
    "            max_len = max(max_len, dp[i][0])\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp = [[0, 0] for i in range(1 + len(nums))]\n",
    "        rsl = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                dp[i+1][0] = dp[i][0] + 1 if dp[i][0] > 0 else 1\n",
    "                dp[i+1][1] = dp[i][1] + 1 if dp[i][1] > 0 else dp[i][1]\n",
    "            elif nums[i] < 0:\n",
    "                dp[i + 1][0] = dp[i][1] + 1 if dp[i][1] > 0 else dp[i][1]\n",
    "                dp[i + 1][1] = dp[i][0] + 1 if dp[i][0] > 0 else 1\n",
    "            rsl = max(rsl, dp[i+1][0])\n",
    "        return rsl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        leftPositive = [0] * n\n",
    "        leftNegative = [0] * n\n",
    "        if nums[0] > 0:\n",
    "            leftPositive[0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            leftNegative[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > 0:\n",
    "                leftPositive[i] = leftPositive[i - 1] + 1\n",
    "                if leftNegative[i - 1] > 0:\n",
    "                    leftNegative[i] = leftNegative[i - 1] + 1\n",
    "            elif nums[i] < 0:\n",
    "                if leftNegative[i - 1] > 0:\n",
    "                    leftPositive[i] = leftNegative[i - 1] + 1\n",
    "                leftNegative[i] = leftPositive[i - 1] + 1\n",
    "        rightPositive = [0] * n\n",
    "        rightNegative = [0] * n\n",
    "        if nums[n - 1] > 0:\n",
    "            rightPositive[n - 1] = 1\n",
    "        elif nums[n - 1] < 0:\n",
    "            rightNegative[n - 1] = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] > 0:\n",
    "                rightPositive[i] = rightPositive[i + 1] + 1\n",
    "                if rightNegative[i + 1] > 0:\n",
    "                    rightNegative[i] = rightNegative[i + 1] + 1\n",
    "            elif nums[i] < 0:\n",
    "                if rightNegative[i + 1] > 0:\n",
    "                    rightPositive[i] = rightNegative[i + 1] + 1\n",
    "                rightNegative[i] = rightPositive[i + 1] + 1\n",
    "\n",
    "        result = rightPositive[n - 1]\n",
    "        for i in range(n - 1):\n",
    "            result = max(result, leftPositive[i] + rightPositive[i + 1])\n",
    "            if leftNegative[i] > 0 and rightNegative[i + 1] > 0:\n",
    "                result = max(result, leftNegative[i] + rightNegative[i + 1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        # 找非0的数组\n",
    "        new = []\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] == 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                temp = []\n",
    "                while i < len(nums) and nums[i]:\n",
    "                    temp.append(nums[i])\n",
    "                    i += 1\n",
    "                new.append(temp)\n",
    "        \n",
    "        \n",
    "        nums = new\n",
    "        # 找到每一个不包含0的数组中的最长正数子数组        \n",
    "        # 动态规划\n",
    "        # d[i] = [正数长度，负数长度]\n",
    "        # d[i] = if nums[i]为正数，则均加一；if nums[i]为负数，则调转加一；if nums[i]为0，则长度为0\n",
    "        # d[-1] = [正数长度，负数长度，否]\n",
    "        def getLongest(arr):\n",
    "            d = [[0, 0] for _ in range(len(arr))]\n",
    "            for i in range(len(arr)-1, -1, -1):\n",
    "                if i == len(arr)-1:\n",
    "                    if arr[i] < 0:\n",
    "                        d[i] = [0, 1]\n",
    "                    else: \n",
    "                        d[i] = [1, 0]\n",
    "                else:\n",
    "                    if arr[i] < 0:\n",
    "                        if d[i+1][1] == 0:\n",
    "                            d[i] = [0, d[i+1][0]+1]\n",
    "                        elif d[i+1][0] == 0:\n",
    "                            d[i] = [d[i+1][1]+1, 1]\n",
    "                        else:\n",
    "                            d[i] = [d[i+1][1]+1, d[i+1][0]+1]\n",
    "                    else:\n",
    "                        if d[i+1][0] == 0:\n",
    "                            d[i] = [1, d[i+1][1]+1]\n",
    "                        elif d[i+1][1] == 0:\n",
    "                            d[i] = [d[i+1][0]+1, 0]\n",
    "                        else:\n",
    "                            d[i] = [d[i+1][0]+1, d[i+1][1]+1]\n",
    "            \n",
    "            return sorted(d, key=lambda x:x[0], reverse=True)[0][0]\n",
    "        \n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if res < getLongest(num):\n",
    "                res = getLongest(num)\n",
    "        return res\n",
    "                            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [(0, 0)]\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            a,b=dp[-1]\n",
    "            if num==0:\n",
    "                dp.append((0,0))\n",
    "            elif num>0:\n",
    "                c,d = a+1, 0\n",
    "                if b>0:\n",
    "                    d=1+b\n",
    "                dp.append((c,d))\n",
    "            elif num<0:\n",
    "                c,d = 0, a+1\n",
    "                if b>0:\n",
    "                    c=1+b\n",
    "                dp.append((c,d))\n",
    "            res=max(res,dp[-1][0])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        L = len(nums)\n",
    "        dp = [[0, 0] for i in range(L + 1)]\n",
    "        for i in range(1, L + 1):\n",
    "            n = nums[i - 1]\n",
    "            if n == 0: continue\n",
    "            if n < 0: \n",
    "                dp[i][1] = dp[i - 1][0] + 1 if dp[i - 1][0] else 0\n",
    "                dp[i][0] = dp[i - 1][1] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0] + 1 if dp[i - 1][0] else 0\n",
    "                dp[i][1] = dp[i - 1][1] + 1\n",
    "        \n",
    "        return max(map(lambda s: s[1], dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0, -inf] for _ in range(n+1)]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] > 0:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = dp[i-1][1] + 1\n",
    "            elif nums[i-1] < 0:\n",
    "                dp[i][0] = max(dp[i-1][1] + 1, 0)\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = -inf\n",
    "            ans = max(dp[i][0], ans)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums_len = len(nums)\n",
    "        dp = [[0]*2 for _ in range(nums_len)]\n",
    "        ans = 0\n",
    "        if nums[0] >0:\n",
    "            dp[0][0] = 1\n",
    "            ans = 1\n",
    "        elif nums[0] <0:\n",
    "            dp[0][1] = 1\n",
    "            \n",
    "        for i in range(1, nums_len):\n",
    "            if nums[i] >0:\n",
    "                if dp[i-1][0]:\n",
    "                    dp[i][0] = dp[i-1][0]+1\n",
    "                else:\n",
    "                    dp[i][0] = 1\n",
    "                if dp[i-1][1]:\n",
    "                    dp[i][1]=  dp[i-1][1]+1\n",
    "                else:\n",
    "                    dp[i][1] = 0\n",
    "            elif nums[i] == 0:\n",
    "                dp[i] = [0,0]\n",
    "            else:\n",
    "                if dp[i-1][0]:\n",
    "                    dp[i][1] = dp[i-1][0]+1\n",
    "                else:\n",
    "                    dp[i][1] = 1\n",
    "                if dp[i-1][1]:\n",
    "                    dp[i][0] =  dp[i-1][1]+1\n",
    "                else:\n",
    "                    dp[i][0] = 0\n",
    "            if dp[i][0] > ans:\n",
    "                ans =  dp[i][0]\n",
    "        # print(dp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums_len = len(nums)\n",
    "        dp = [[0]*2 for _ in range(nums_len)]\n",
    "        ans = 0\n",
    "        if nums[0] >0:\n",
    "            dp[0][0] = 1\n",
    "            ans = 1\n",
    "        elif nums[0] <0:\n",
    "            dp[0][1] = 1\n",
    "            \n",
    "        for i in range(1, nums_len):\n",
    "            if nums[i] >0:\n",
    "                if dp[i-1][0]:\n",
    "                    dp[i][0] = dp[i-1][0]+1\n",
    "                else:\n",
    "                    dp[i][0] = 1\n",
    "                if dp[i-1][1]:\n",
    "                    dp[i][1]=  dp[i-1][1]+1\n",
    "                else:\n",
    "                    dp[i][1] = 0\n",
    "            elif nums[i] == 0:\n",
    "                dp[i] = [0,0]\n",
    "            else:\n",
    "                if dp[i-1][0]:\n",
    "                    dp[i][1] = dp[i-1][0]+1\n",
    "                else:\n",
    "                    dp[i][1] = 1\n",
    "                if dp[i-1][1]:\n",
    "                    dp[i][0] =  dp[i-1][1]+1\n",
    "                else:\n",
    "                    dp[i][0] = 0\n",
    "            if dp[i][0] > ans:\n",
    "                ans =  dp[i][0]\n",
    "        # print(dp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def getMaxLen(self, nums) :\n",
    "    n = len(nums)\n",
    "    dp = [[0] *2 for _ in range(n)]\n",
    "    dp[0][0], dp[0][1] = int(nums[0] > 0), int(nums[0] < 0)\n",
    "    ans = dp[0][0]\n",
    "    for i in range(1, n):\n",
    "      num = nums[i]\n",
    "      if num > 0:\n",
    "        dp[i][0] = dp[i - 1][0] + 1\n",
    "        dp[i][1] = dp[i - 1][1] + 1 if dp[i - 1][1] > 0 else 0\n",
    "      elif num == 0:\n",
    "        dp[i][0] = dp[i][1] = 0\n",
    "      else:\n",
    "        dp[i][0] = dp[i - 1][1] + 1 if dp[i - 1][1] > 0 else 0\n",
    "        dp[i][1] = dp[i - 1][0] + 1\n",
    "      ans = max(ans, dp[i][0])\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        dp = [None] * l\n",
    "        p = 1 if nums[0] > 0 else 0\n",
    "        n = 1 if nums[0] < 0 else 0\n",
    "        ret = p\n",
    "        dp[0] = [p, n]\n",
    "        for i in range(1, l):\n",
    "            v = nums[i]\n",
    "            pd = dp[i - 1]\n",
    "            p, n = 0, 0\n",
    "            if v > 0:\n",
    "                p = pd[0] + 1\n",
    "                n = pd[1] + 1 if pd[1] > 0 else 0\n",
    "            elif v < 0:\n",
    "                p = pd[1] + 1 if pd[1] > 0 else 0\n",
    "                n = pd[0] + 1\n",
    "            dp[i] = [p, n]\n",
    "            ret = max(ret, p)\n",
    "        # print(dp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # dp[i][0]: nums[0~i]中乘积为正数的最长子数组\n",
    "        # dp[i][1]: nums[0~i]中乘积为负数的最长子数组\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "\n",
    "        if nums[0] > 0:\n",
    "            dp[0][0] = 1\n",
    "        elif nums[0] < 0:\n",
    "            dp[0][1] = 1\n",
    "        \n",
    "        ans = dp[0][0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > 0:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                # 正*负\n",
    "                if dp[i-1][1] > 0:\n",
    "                    dp[i][1] = dp[i-1][1] + 1\n",
    "            elif nums[i] < 0:\n",
    "                if dp[i-1][1] > 0:\n",
    "                    dp[i][0] = dp[i-1][1] + 1\n",
    "                # 正*负\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i][1] = 0\n",
    "            \n",
    "            ans = max(ans, dp[i][0])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp[i][0]表示以nums[i]结尾的乘机为“正数”的最长子数组\n",
    "        # dp[i][1]表示以nums[i]结尾的乘机为“负数”的最长子数组\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "\n",
    "        if nums[0] < 0:\n",
    "            dp[0][1] = 1\n",
    "        elif nums[0] > 0:\n",
    "            dp[0][0] = 1\n",
    "\n",
    "        res = dp[0][0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] < 0:\n",
    "                dp[i][0] = dp[i-1][1] + 1 if dp[i-1][1] > 0 else 0\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            elif nums[i] > 0:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = dp[i-1][1] + 1 if dp[i-1][1] > 0 else 0\n",
    "            else:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = 0\n",
    "            res = max(res, dp[i][0])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp = [[0, 0] for _ in range(len(nums))]\n",
    "        max_len = 0\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = (dp[i - 1][1] + 1) if dp[i - 1][1] else 0\n",
    "            elif nums[i] < 0:\n",
    "                dp[i][0] = (dp[i - 1][1] + 1) if dp[i - 1][1] else 0\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "            max_len = max(max_len, dp[i][0])\n",
    "        return max_len                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp = [[0, 0] for _ in range(len(nums))]\n",
    "        max_len = 0\n",
    "        if nums[0] > 0:\n",
    "            dp[0][0] = 1\n",
    "            max_len = 1\n",
    "        elif nums[0] < 0:\n",
    "            dp[0][1] = 1\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                dp[i][1] = (dp[i - 1][1] + 1) if dp[i - 1][1] else 0\n",
    "            elif nums[i] < 0:\n",
    "                dp[i][0] = (dp[i - 1][1] + 1) if dp[i - 1][1] else 0\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "            max_len = max(max_len, dp[i][0])\n",
    "        for d in dp:\n",
    "            print(d)\n",
    "        return max_len                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp = [[0 for i in range(2)] for j in range(len(nums))]\n",
    "        max_len = 1 if nums[0] > 0 else 0\n",
    "        if nums[0] == 0:\n",
    "            dp[0][0] = dp[0][1] = 0\n",
    "        elif nums[0] > 0:\n",
    "            dp[0][0] = 0\n",
    "            dp[0][1] = 1\n",
    "        elif nums[0] < 0:\n",
    "            dp[0][0] = 1\n",
    "            dp[0][1] = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = 0\n",
    "            elif nums[i] > 0:\n",
    "                dp[i][0] = dp[i - 1][0] + 1 if dp[i - 1][0] > 0 else 0\n",
    "                dp[i][1] = dp[i - 1][1] + 1\n",
    "            elif nums[i] < 0:\n",
    "                dp[i][0] = dp[i - 1][1] + 1\n",
    "                dp[i][1] = dp[i - 1][0] + 1 if dp[i - 1][0] > 0 else 0\n",
    "            if dp[i][1] > max_len:\n",
    "                max_len = dp[i][1]\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if not nums: return 0\n",
    "        N = len(nums)\n",
    "        dp = [[0,0] for _ in range(N)]\n",
    "        if nums[0]>0:\n",
    "            dp[0][0] += 1\n",
    "            ans = 1\n",
    "        elif nums[0]<0:\n",
    "            dp[0][1] += 1\n",
    "\n",
    "        for i in range(1, N):\n",
    "            n = nums[i]\n",
    "            if n>0:\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                if dp[i-1][1]!=0:\n",
    "                    dp[i][1] = dp[i-1][1]+1\n",
    "            elif n<0:\n",
    "                if dp[i-1][1]!=0:\n",
    "                    dp[i][0] = dp[i-1][1]+1\n",
    "                dp[i][1] = dp[i-1][0]+1\n",
    "            ans = max(ans, dp[i][0])\n",
    "        print(dp)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[[0]*3 for _ in range(n)]\n",
    "        if nums[0]>0:\n",
    "            dp[0][0]=1\n",
    "        elif nums[0]<0:\n",
    "            dp[0][1]=1\n",
    "        else:\n",
    "            dp[0][2]=1\n",
    "        res=dp[0][0]\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>0:\n",
    "                dp[i][0]=dp[i-1][0]+1\n",
    "                if dp[i-1][1]>0:\n",
    "                    dp[i][1]=dp[i-1][1]+1\n",
    "                if dp[i-1][2]>0:\n",
    "                    dp[i][2]=dp[i-1][2]+1\n",
    "            elif nums[i]<0:\n",
    "                dp[i][1]=dp[i-1][0]+1\n",
    "                if dp[i-1][1]>0:\n",
    "                    dp[i][0]=dp[i-1][1]+1\n",
    "                if dp[i-1][2]>0:\n",
    "                    dp[i][2]=dp[i-1][2]+1\n",
    "            else:\n",
    "                dp[i][2]=dp[i-1][2]+1\n",
    "            res=max(res,dp[i][0])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "s=Solution()\n",
    "print(s.getMaxLen([-1,-2,-3,0,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        dp = [[0, 0] for _ in range(len(nums))]\n",
    "        res = 0\n",
    "        if nums[0] > 0:\n",
    "            dp[0][0] = 1\n",
    "            res = 1\n",
    "        elif nums[0] < 0:\n",
    "            dp[0][1] = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                if dp[i-1][1] != 0:\n",
    "                    dp[i][1] = dp[i-1][1] + 1\n",
    "            elif nums[i] == 0:\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = 0\n",
    "            else:\n",
    "                if dp[i-1][1] != 0:\n",
    "                    dp[i][0] = dp[i-1][1] + 1\n",
    "                dp[i][1] = dp[i-1][0] + 1\n",
    "            res = max(res, dp[i][0])\n",
    "        print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        N=len(nums)\n",
    "        dp=[[0]*2 for i in range(N)]\n",
    "        ans=0\n",
    "        if nums[0]>0:\n",
    "            dp[0][1]=1\n",
    "            ans=1\n",
    "        if nums[0]<0:\n",
    "            dp[0][0]=1\n",
    "            ans=0\n",
    "        \n",
    "        for i in range(1,N):\n",
    "            if nums[i]>0:\n",
    "                dp[i][1]=dp[i-1][1]+1\n",
    "                if dp[i-1][0]!=0:\n",
    "                    dp[i][0]=dp[i-1][0]+1\n",
    "                \n",
    "            elif nums[i]<0:\n",
    "                dp[i][0]=dp[i-1][1]+1\n",
    "                if dp[i-1][0]!=0:\n",
    "                    dp[i][1]=dp[i-1][0]+1\n",
    "            ans=max(ans,dp[i][1])\n",
    "        print(dp)\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        dp = [[0,0] for _ in range(l)]\n",
    "        if nums[0] > 0:\n",
    "            dp[0][0] = 1\n",
    "            dp[0][1] = 0\n",
    "        elif nums[0] < 0:\n",
    "            dp[0][0] = 0\n",
    "            dp[0][1] = 1\n",
    "        for i in range(1,l):\n",
    "            if nums[i] > 0:\n",
    "                dp[i][0] = dp[i - 1][0] + 1 if dp[i - 1][0] != 0 else 1\n",
    "                dp[i][1] = dp[i - 1][1] + 1 if dp[i - 1][1] != 0 else 0\n",
    "            elif nums[i] < 0:\n",
    "                dp[i][0] = dp[i - 1][1] + 1 if dp[i - 1][1] != 0 else 0\n",
    "                dp[i][1] = dp[i - 1][0] + 1 if dp[i - 1][0] != 0 else 1\n",
    "                \n",
    "                \n",
    "            \n",
    "        res = 0\n",
    "        print(dp)\n",
    "        for i in range(l):\n",
    "            res = max(res,dp[i][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        for i, v in enumerate(nums):\n",
    "            pre_pos, pre_neg = dp[i - 1]\n",
    "            if v > 0:\n",
    "                dp[i] = [pre_pos + 1, pre_neg and pre_neg + 1]\n",
    "            if v < 0:\n",
    "                dp[i] = [pre_neg and pre_neg +1 , pre_pos+1]\n",
    "            if v == 0:\n",
    "                dp[i] = [0, 0]\n",
    "        print(dp)\n",
    "        return max(dp)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        dp[i][0] 表示乘积为正数的最大子数组长度\n",
    "        dp[i][1] 表示乘积为负数的最大子数组长度\n",
    "    '''\n",
    "    def getMaxLen(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0 for _ in range(2)] for _ in range(n)]\n",
    "        if nums[0] > 0:\n",
    "            dp[0][0] = 1\n",
    "        elif nums[0] < 0: \n",
    "            dp[0][1] = 1\n",
    "        ans = dp[0][0]\n",
    "        for i in range(1, n):\n",
    "            if nums[i] > 0:                 # 当前是正数\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "                if dp[i - 1][1] != 0:\n",
    "                    dp[i][1] = dp[i - 1][1] + 1    \n",
    "            elif nums[i] < 0:               # 当前是负数\n",
    "                dp[i][1] = dp[i - 1][0] + 1\n",
    "                if dp[i - 1][1] != 0:\n",
    "                    dp[i][0] = dp[i - 1][1] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i][1] = 0\n",
    "            ans = max(ans, dp[i][0])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
